import java.util.Map;

/**
 * Created by zhang_j on 2020/7/1
 */
public class 最长重复子数组 {

    public static void main(String[] args) {
        int[] a = {5,4,3,2,1};
        int[] b = {3,2,1,6,4};
        System.out.println(findLength(a, b));
        System.out.println(findLengthBySlidingWindow(a, b));
    }

    public static int findLengthBySlidingWindow(int[] A, int[] B){
        if (A == null || B == null){
            return 0;
        }
        int m = A.length;
        int n = B.length;
        if(m == 0 || n == 0){
            return 0;
        }
        int length = m + n - 1;
        int max = 0;
        for(int i = 0;i < length;i++){
            int aStart, bStart, len;
            if(i < m){
                aStart = m - i - 1;
                bStart = 0;
                len = i + 1;
            }else{
                aStart = 0;
                bStart = i - m + 1;
                len = Math.min(n - bStart, m);
            }
            max = Math.max(max, getMax(A, B, aStart, bStart, len));
        }
        return max;
    }

    private static int getMax(int[] A, int[] B, int aStart, int bStart, int len){
        int max = 0, count = 0;
        int j = bStart;
        for(int i = aStart;i < aStart + len && j < bStart + len;i++){
            if(A[i] == B[j++]){
                count++;
                max = Math.max(max, count);
            }else{
                count = 0;
            }
        }
        return max;
    }

    public static int findLength(int[] A, int[] B) {
        if (A == null || B == null){
            return 0;
        }
        int m = A.length;
        int n = B.length;
        if(m == 0 || n == 0){
            return 0;
        }
        int max = 0;
        int[][] dp = new int[m][n];
        for(int i = 0;i < m;i++){
            dp[i][0] = A[i] == B[0] ? 1 : 0;
        }
        for(int j = 0;j < n;j++){
            dp[0][j] = A[0] == B[j] ? 1 : 0;
        }
        for(int i = 1;i < m;i++){
            for(int j = 1;j < n;j++){
                if(B[j] == A[i]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = 0;
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }
}
